package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/majority-element/description/">多数元素(Majority Element)</a>
 * <p>
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [3,2,3]
 *      输出：3
 *
 * 示例 2：
 *      输入：nums = [2,2,1,1,1,2,2]
 *      输出：2
 * </pre>
 * </p>
 * <b>提示：</b>
 * <ul>
 *     <li>n == nums.length</li>
 *     <li>1 <= n <= 5 * 10^4</li>
 *     <li>-10^9 <= nums[i] <= 10^9</li>
 * </ul>
 *
 * <b>进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。</b>
 *
 * @author c2b
 * @see LC0169MajorityElement_S 多数元素(Majority Element)
 * @see LC0229MajorityElement_II_M 多数元素 II(Majority Element II)
 * @since 2023/10/9 16:58
 */
public class LC0169MajorityElement_S {
    static class Solution {
        /**
         * “数组中出现次数超过一半的数字” 被称为 “众数” 。
         * <p>Boyer-Moore 投票算法：如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。</p>
         */
        public static int majorityElement(int[] nums) {
            // 假设多数元素为0，多数元素出现的次数也为0
            int majorityElement = 0;
            int count = 0;
            for (int num : nums) {
                // 当 票数 votes 等于 0 ，则假设当前数字 num 是众数。
                if (count == 0) {
                    majorityElement = num;
                    count = 1;
                } else {
                    // 当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 。
                    count += (majorityElement == num) ? 1 : -1;
                }
            }
            return majorityElement;
        }
    }

    public static void main(String[] args) {
        int majorityElement = Solution.majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2});
        System.out.println(majorityElement);
    }
}
